/*
day363 
2020.8.25 
*/
#include<iostream>
#include<algorithm>
#include<unordered_map> 
#include<vector>
using namespace std; 


class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
		int sum=0;
		unordered_map<int,int> m;
		m[0]=1;
		for(int i=0;i<A.size();++i)
		{
			sum+=A[i];
			while(sum<0)
			{
				sum+=K;
			}
			sum%=K;
			m[sum]++;
		}
		
		int res=0; 
		for(auto & i : m)
		{
			int n=i.second;
			res+=n*(n-1)/2;
		} 
		
		return res;
    }
};

int main()
{
	vector<int> A = {4,5,0,-2,-3,1};
	int K = 5;
	Solution s;
	int res=s.subarraysDivByK(A,K);
	cout<<res<<endl;
	return 0;
}
